package com.example.lcpractice.heading_offer;

import com.example.lcpractice.datastructure.TreeNode;
import lombok.Getter;

import java.util.HashMap;

/**
 * 输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
 * <p>
 * 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 * <p>
 * 示例 1:
 * <p>
 * <p>
 * Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
 * Output: [3,9,20,null,null,15,7]
 * 示例 2:
 * <p>
 * Input: preorder = [-1], inorder = [-1]
 * Output: [-1]
 * 限制：
 * <p>
 * 0 <= 节点个数 <= 5000
 */
@Getter
public class q07 {
 /*   @Data
    //树节点定义
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }*/

    //前序数组
    static int[] preorder;
    //中序数组
    static int[] inorder;

    /**
     * 存放中序遍历的  <u><数值,出现的序数></u>
     */
    static HashMap<Integer, Integer> inOrderIndexDic = new HashMap<>();

    public static void main(String[] args) {
        preorder = new int[]{3, 9, 20, 15, 7};
        inorder = new int[]{9, 3, 15, 20, 7};
        System.out.println(buildTree(preorder, inorder));

    }

    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            inOrderIndexDic.put(inorder[i], i);
        }
        return recur(0, 0, inorder.length - 1);
    }

    /**
     * 递归公式
     * Node root=new Node(根数值)
     * root.left=recur(前序左子树，中序左子树)
     * root.right=recur(前序左子树，中序左子树)
     *
     * @param root  根节点数值在前序遍历数组 <b>preorder</b> 的序数
     * @param left
     * @param right
     * @return 根节点
     */
    static TreeNode recur(int root, int left, int right) {
        if (left > right) {
            return null;                          // 递归终止
        }
        // 子树的根节点
        TreeNode node = new TreeNode(preorder[root]);          // 建立根节点
        // preorder[root] 根节点数值； 得出在中序遍历中的序数
        // i为中序数组  根 序数，（(left),(i-1))为中序数组左边的左子树
        // i为中序数组中 根 序数，（(i+1),(right))为中序数组左边的右子树
        // (root+1)为递归后左子树先序遍历的第一个，也就是新的根节点的序数
        // (root+i-left+1)为右子树先序遍历第一个。。。
        int i = inOrderIndexDic.get(preorder[root]);                       // 划分根节点、左子树、右子树
        node.setLeft(recur(root + 1, left, i - 1));              // 开启左子树递归
        node.setRight(recur(root + i - left + 1, i + 1, right)); // 开启右子树递归
        return node;                                           // 回溯返回根节点
    }
}
